from typing import List


class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        sumMap = {}
        s, result = 0, 0
        for i in range(len(hours)):
            s += 1 if hours[i] > 8 else -1
            if s > 0:
                result = max(result, i+1)
            else:
                if s-1 in sumMap:
                    result = max(result, i-sumMap[s-1])

            if s not in sumMap:
                sumMap[s] = i

        return result

    def longestWPI_Wrong(self, hours: List[int]) -> int:
        work = [1 if x > 8 else -1 for x in hours]
        result = 0
        i, k = 0, len(work)
        while i < k:
            total = sum(work[i:k])
            if total > 0:
                result = k-i
                break
            else:
                if work[i] < 0:
                    i += 1
                elif work[k-1] < 0:
                    k -= 1
                else:
                    center = (i+k)//2
                    if (i+k) % 2 == 0:
                        if sum(work[i:center]) > sum(work[center+1:k]):
                            k -= 1
                        else:
                            i += 1
                    else:
                        if sum(work[i:center+1]) > sum(work[center:k]):
                            k -= 1
                        else:
                            i += 1

        return result


# print(Solution().longestWPI([13, 4, 2, 5, 0, 6, 0, 10, 5, 12, 5]))
print(Solution().longestWPI([6, 6, 5, 7, 5, 9, 9, 9, 7, 8, 5, 9, 8, 7, 9, 9, 6, 6, 7, 9, 6, 10, 9, 10, 5, 7, 6, 10, 8, 6, 8, 10, 5, 6, 7, 9, 6, 5, 8, 6, 6, 10, 5, 9, 9, 5,
      6, 8, 6, 5, 9, 6, 9, 6, 10, 9, 8, 9, 8, 7, 7, 5, 5, 9, 7, 8, 6, 10, 5, 6, 5, 6, 9, 5, 9, 8, 7, 10, 10, 5, 9, 9, 8, 6, 8, 7, 9, 6, 9, 7, 6, 9, 5, 5, 7, 10, 6, 5, 10, 5]))
